<?xml version="1.0" encoding="ISO-8859-1"?>
<metadatalist>
	<metadata ReferenceType="Thesis">
		<site>marte3.sid.inpe.br 804</site>
		<holdercode>{isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S}</holdercode>
		<identifier>6qtX3pFwXQZ3r59YCT/GUJkQ</identifier>
		<repository>sid.inpe.br/iris@1905/2005/07.29.21.34.16</repository>
		<lastupdate>2013:04.24.18.44.41 sid.inpe.br/banon/2001/04.03.15.36 simone</lastupdate>
		<metadatarepository>sid.inpe.br/iris@1905/2005/07.29.21.34.20</metadatarepository>
		<metadatalastupdate>2019:10.07.19.15.46 sid.inpe.br/banon/2001/04.03.15.36 simone {D 1998}</metadatalastupdate>
		<secondarykey>INPE-7250-TDI/694</secondarykey>
		<label>8583</label>
		<citationkey>Yamamoto:1998:ApBuTa</citationkey>
		<title>Uma aplicação da Busca Tabu ao problema de rotulação cartográfica de pontos</title>
		<alternatetitle>Tabu search application for point features cartographic label placement problem</alternatetitle>
		<course>CAP-SPG-INPE-MCT-BR</course>
		<year>1998</year>
		<secondarydate>19991013</secondarydate>
		<date>1998-12-18</date>
		<thesistype>Dissertação (Mestrado em Computação Aplicada)</thesistype>
		<secondarytype>TDI</secondarytype>
		<numberofpages>132</numberofpages>
		<numberoffiles>1</numberoffiles>
		<size>1989 KiB</size>
		<author>Yamamoto, Missae,</author>
		<group>CAP-SPG-INPE-MCT-BR</group>
		<committee>Carvalho, Solon Venâncio de (presidente),</committee>
		<committee>Lorena, Luiz Antonio Nogueira (orientador),</committee>
		<committee>Câmara Neto, Gilberto (orientador),</committee>
		<committee>Scrich, Cintia Rigão,</committee>
		<committee>Carvalho, Paulo Cezar Pinto,</committee>
		<university>Instituto Nacional de Pesquisas Espaciais (INPE)</university>
		<city>Sao Jose dos campos</city>
		<transferableflag>1</transferableflag>
		<keywords>Busca Tabu, rotulação cartográfica, algoritmo de otimização, produção cartografica automatizada, sistemas de informação geográfica, SGI, GIS, tabu search, label placement, heuristic.</keywords>
		<abstract>A geração de configurações ótimas de rótulos em um mapa e um problema que surge com a produção cartográfica automatizada. O objetivo de uma boa rotulação e mostrar a posição geográfica das entidades com texto associado, de forma legível, e respeitando as convenções cartográficas, com qualidades estética e harmônica na apresentação dessas informações. Abordamos o problema de rotulação cartográfica sob o ponto de vista de otimização combinatória. Nesta perspectiva, a rotulação cartográfica pertence a classe de problemas de difícil solução, conduzindo-nos a necessidade de algoritmos de aproximação, uma vez que não existe nenhum algoritmo exato capaz de soluciona-lo em um intervalo de tempo aceitável. Nossa pesquisa consistiu na avaliação do algoritmo de otimização Busca Tabu aplicado a rotulação cartográfica. A Busca Tabu implementada no SCARTA, um software de produção cartográfico em desenvolvimento pela Divisão de Processamento de Imagens do Instituto Nacional de Pesquisas Espaciais, mostrou-se um algoritmo eficiente, nos casos-teste real e aleatório, Quando comparado a técnicas alternativas como "Simulated Annealing", algoritmo genético com mascara, e outras descritas na literatura, a Busca Tabu apresentou o melhor desempenho em qualidade. Concluímos que a Busca Tabu e um método recomendável para solução de problema de rotulação cartográfica de pontos, devido a sua simplicidade, praticidade, eficiência e bom desempenho, conjugado a capacidade de gerar soluções de qualidade em tempo computacional aceitável. ABSTRACT: The generation of better label placement configurations in maps is a problem that comes up in automated cartographic production. The objective of a good label placement is to show the geographic position of the features with their corresponding texts clearly, respecting the cartographic conventions, with an esthetic and a harmonious qua when presenting the information. We approached the label placement problem from a combinatorial optimization point of view. In this perspective, the cartographic label placement belongs to a problem area of difficult solution, leading us to the need of approximation algorithms as there is no exact algorithm that is able to solve this problem within an acceptable amount of time. Our research consisted in the evaluation of the tabu search optimization algorithm applied to cartographic label placement. The tabu search implemented in SCARTA, a cartographic production software, in development by the Image Processing Division of the National Institute of Aerospace Researches, proved to be an efficient algorithm, in real and random test cases. When compared with alternative techniques such as simulated annealing, genetic algorithm with mask and others described in literature, the tabu search had the best performance in quality. We concluded that tabu search is a recommended method to solve cartographic label placement problem of point features, due to its simplicity, practicality, efficiency and good performance along with its ability to generate quality solutions in acceptable computational time.</abstract>
		<area>COMP</area>
		<language>pt</language>
		<targetfile>publicacao.pdf</targetfile>
		<usergroup>administrator</usergroup>
		<usergroup>jefferson</usergroup>
		<usergroup>sergio@sid.inpe.br</usergroup>
		<usergroup>tereza@sid.inpe.br</usergroup>
		<visibility>shown</visibility>
		<copyright>urlib.net/www/2012/11.12.15.15</copyright>
		<rightsholder>originalauthor yes</rightsholder>
		<copyholder>SID/SCD</copyholder>
		<readpermission>allow from all</readpermission>
		<documentstage>not transferred</documentstage>
		<nexthigherunit>8JMKD3MGPCW/3F2PHGS</nexthigherunit>
		<dissemination>NTRSNASA; BNDEPOSITOLEGAL.</dissemination>
		<hostcollection>sid.inpe.br/banon/2001/04.03.15.36</hostcollection>
		<agreement>{termo de deposito Missae.pdf} .htaccess .htaccess2</agreement>
		<lasthostcollection>sid.inpe.br/banon/2001/04.03.15.36</lasthostcollection>
		<supervisor>Câmara Neto, Gilberto,</supervisor>
		<supervisor>Lorena, Luiz Antonio Nogueira,</supervisor>
		<url>http://marte3.sid.inpe.br/rep-/sid.inpe.br/iris@1905/2005/07.29.21.34.16</url>
	</metadata>
</metadatalist>